% !TEX root = ArticoloRF.tex
%gini project detail
\subsection{Gini Index}\label{sec:gini}
The Gini Index \cite{giniindex} is a real number in the range $\lbrace 0 \ldots 1 \rbrace$ that measures statistical dispersion. A Gini coefficient of 0 expresses a perfect equality among a set of data with only one possible value, while a Gini coefficient approximately equal to 1 expresses a maximum dispersion, with each single value appearing just once in the whole set. With a Gini Index based approach, the function $f(\mathbf{x})$ defined above takes the following form
\[ f(\mathbf{x})=f(\mathbf{x},\mathbf{w})  = \mathbf{w}\tran\mathbf{x}\]
where $\mathbf{w}$ is defined as
\[ \mathbf{w}\tran = \begin{bmatrix}w_{1}&w_{2}&\cdots&w_{n}\end{bmatrix} \]
and each $w_{i}$ is subject to the following conditions
\[ w_{i} \in \{0,1\} \]
\[ \sum_{j=0}^{n} w_{j} = 1\]
If $w_{i}$ is equal to 1, $f(\mathbf{x},\mathbf{w})$ gives in output $x_i$, which is the value of the $i^{th}$ feature of record $\mathbf{x}$. In the context of decision trees, Gini Index becomes useful while evaluating the best split in the $n$ dimensional input space, allowing to find that particular pair of split function and threshold which leads to the minimum dispersion of classes in the two child nodes. Considering a parent node associated with a set of data $\mathbf{V} \in \mathbb{R}^{m \times n+1}$ and a pair of split function $f(\mathbf{x},\mathbf{w})$ and threshold $t$ that yields two child nodes with subsets $\mathbf{S}_{R} \in \mathbb{R}^{r \times n+1}$ and $\mathbf{S}_{L} \in \mathbb{R}^{u \times n+1} $, where the former belongs to the right node and the latter to the left one, the algorithm based on the Gini coefficient computes the following value
\[ \mathrm{gini}(\mathbf{S}_{s}) = 1 - \sum_{j=0}^{C} p_{j,s}^2 \]
where $s \in \{R,L\}$, $p_{j,s}$ is the probability to encounter the $j^{th}$ class in the subset $\mathbf{S}_{s}$ and $C$ is the number of different classes available for the classification problem. These indexes are then weighted for the number of records in each node in order to obtain a final Gini score
\[ G(\mathbf{X}, f, t) = \frac{r}{m} \mathrm{gini}(\mathbf{S}_{R}) + \frac{u}{m} \mathrm{gini}(\mathbf{S}_{L}) \]
$G(\mathbf{X},f,t)$ is evaluated over all possible pairs $(f, t)$, and the instance $(\bar{f}, \bar{t})$ that minimizes the value of $G(\mathbf{X}, f, t)$ is used to split the parent node. In order to find the best pair of $f$ and $t$, the algorithm loops over all the possible $\mathbf{w}$ (i.e. over all the available features) and for each $\mathbf{\bar{w}}$, assuming $\mathbf{\bar{w}}_j$ = 1, it sorts the following set

\[ \{ \mathbf{\bar{w}}\tran \mathbf{x} : \mathbf{x} \in \mathbf{X} \} = \{x_{1,j}, x_{2,j} \ldots x_{m,j} \} \]

Once the set is ordered, the algorithm iterates over every $x_{i,j}$ with $i \in \{1 \ldots m-1\}$ and if $x_{i,j} \neq x_{i+1,j}$, it computes $t$ as

\[ t = \frac{x_{i,j} + x_{i+1,j}}{2} \]
It then evaluates $G(\mathbf{X}, f, t)$ and if the result is lower than the current minimum value, it updates $(\bar{f}, \bar{t})$. Once nested loops are over, the solution $(\bar{f}, \bar{t})$ is used to create two children nodes. For the purpose of building a forest made of several trees, the algorithm based on the Gini Index evaluation is not a good choice because it is aimed at finding always the best solution available. Thus, every tree added to the forest is always identical to previous ones. A slightly different version of the algorithm tries to solve this issue by reducing the number of features used to find the best split. Hence, the first loop does not iterate over all the possible values of $\mathbf{w}$ but it is restricted to a subset with $\sqrt{n}$ values picked at random, yielding a different  tree at each step which has not been generated by splitting with the best pair $(\bar{f}, \bar{t})$, but with a suboptimal solution that is likely to be better than a random chosen one.





